package com.tucc.hello.leetcode.no1_400.no1_200.no1_20.no1_10.no4;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description:
 * @Date: 2021/5/13 14:52
 * @Author: tucc
 */
public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length == 0 && nums2.length == 0) {
            return 0d;
        }
        boolean needTwo = (0 == (nums1.length + nums2.length) % 2);
        int mIndex = (nums1.length + nums2.length - 1) / 2;
        if (nums1.length == 0) {
            return needTwo ? (nums2[mIndex] + nums2[mIndex + 1]) / 2.0 : nums2[mIndex];
        }
        if (nums2.length == 0) {
            return needTwo ? (nums1[mIndex] + nums1[mIndex + 1]) / 2.0 : nums1[mIndex];
        }
        if(nums1[nums1.length - 1] <= nums2[0]){
            return returnForOrderedTwo(nums1, nums2, needTwo, mIndex);
        }
        if(nums2[nums2.length - 1] <= nums1[0]){
            return returnForOrderedTwo(nums2, nums1, needTwo, mIndex);
        }
        return find(nums1, nums2, needTwo, mIndex);
    }

    public double find(int[] nums1, int[] nums2,
                       boolean needTwo, int mIndex){
        int k = findKthInTwoOrderedArr(nums1, nums2, mIndex + 1);
        return needTwo ? (k + findKthInTwoOrderedArr(nums1, nums2, mIndex + 2)) / 2.0
                : k;
    }

    public int findKthInTwoOrderedArr(int[] num1, int[] num2, int k){
        return findKthInTwoOrderedArr(num1, num2, 0, num1.length - 1, 0, num2.length - 1, k);
    }

    public int findKthInTwoOrderedArr(int[] num1, int[] num2, int l1, int r1,
                                        int l2, int r2, int k){
        if(l1 > r1){
            return num2[l2 + k - 1];
        }
        if(l2 > r2){
            return num1[l1 + k - 1];
        }
        int len1 = r1 - l1;
        int len2 = r2 - l2;
        if(len1 > len2){
            return findKthInTwoOrderedArr(num2, num1, l2, r2, l1, r1, k);
        }
        if(k == 1){
            return Math.min(num1[l1], num2[l2]);
        }
        int m1 = Math.min(l1 + k / 2 - 1, r1);
        int m2 = l2 + k - (m1 - l1) - 2;
        if(num1[m1] < num2[m2]){
            int lose = m1 - l1 + 1;
            return findKthInTwoOrderedArr(num1, num2, l1 + lose, r1, l2, r2, k - lose);
        }
        else if(num2[m2] < num1[m1]){
            int lose = m2 - l2 + 1;
            return findKthInTwoOrderedArr(num1, num2, l1, r1, l2 + lose, r2, k - lose);
        }
        else{
            return num1[m1];
        }
    }

    public double returnForOrderedTwo(int[] first, int[] second, boolean needTwo, int mIndex) {
        return needTwo ? (returnForOrderedTwo(first, second, mIndex)
                + returnForOrderedTwo(first, second, mIndex + 1)) / 2.0
                : returnForOrderedTwo(first, second, mIndex);
    }

    public double returnForOrderedTwo(int[] first, int[] second, int index) {
        return first.length > index ? first[index] :
                second[index - first.length];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
//        System.out.println(solution.findMedianSortedArrays(
//                new int[]{},
//                new int[]{}
//        ));
//        System.out.println(solution.findMedianSortedArrays(
//                new int[]{1},
//                new int[]{}
//        ));
//        System.out.println(solution.findMedianSortedArrays(
//                new int[]{},
//                new int[]{3}
//        ));
//        System.out.println(solution.findMedianSortedArrays(
//                new int[]{1, 2},
//                new int[]{}
//        ));
//        System.out.println(solution.findMedianSortedArrays(
//                new int[]{1},
//                new int[]{2}
//        ));
//        System.out.println(solution.findMedianSortedArrays(
//                new int[]{1, 3},
//                new int[]{4, 5, 6}
//        ));

                System.out.println(solution.findMedianSortedArrays(
                new int[]{1, 3, 4},
                new int[]{2, 5, 6}
        ));
    }
}
